package 数据结构和算法.剑指offer.数组.二维数组中的查找;

import 工具.打印.PrintUtil;

/**
 * 在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。请完成一个函数，
 * 输入这样的一个二维数组和一个整数，判断数组中是否含有该整数
 * <p>
 * 暴力法：暴力匹配，时间复杂度为O(m*n)，空间复杂度为O(1)；
 * 线性查找：对于已经排序好的数组可以使用，从二维数组的右上角开始，如果目标值等于当前值则返回true，如果目标值大于则去下一行，如果小于则去左边一列。
 */
public class Test {
    public static void main(String[] args) {
        int[][] array = new int[][]{{
                1, 2, 3
        }, {
                4, 5, 6
        }};
        PrintUtil.println(findTargetOne(array, 5));
        PrintUtil.println(findTargetTwo(array, 5));
    }

    // 暴力方式
    public static boolean findTargetOne(int[][] array, int target) {
        if (array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }
        for (int i = 0; i < array.length; ++i) {
            for (int j = 0; j < array[i].length; ++j) {
                if (array[i][j] == target) {
                    return true;
                }
            }

        }
        return false;
    }

    // 线性查找方式
    public static boolean findTargetTwo(int[][] array, int target) {
        if (array == null || array.length == 0 || array[0].length == 0) {
            return false;
        }

        int rows = array.length;
        int columns = array[0].length;

        int row = 0;
        int column = columns - 1;
        while (row < rows && column >= 0) {
            if (target == array[row][column]) {
                return true;
            } else if (target < array[row][column]) {
                column--;
            } else {
                row++;
            }
        }

        return false;
    }
}
